package org.wj.problem

object NumTrees {

  def main(args: Array[String]): Unit = {
    println(numTrees(18))
  }

  def numTrees(n: Int): Int = {
    val G =new Array[Int](n+1);
    G(0) = 1
    G(1) = 1
    for(i <- 2 to n){
      for(j <- 1 to i){
        G(i) += G(j-1) * G(i-j)
      }
    }
    G(n)
  }


}
